Legion được đặt hàng cho xưởng tàu của hãng Hawthorn Leslie and Company ở Newcastle upon Tyne vào ngày 31 tháng 3 năm 1938 trong Dự toán Ngân sách Hải quân 1937. Nó được đặt lườn vào ngày 1 tháng 11 năm 1938; được hạ thủy hơn một năm sau đó vào ngày 26 tháng 11 năm 1939. Vào năm 1940, cùng với ba chiếc khác thuộc lớp L, dàn vũ khí chính của nó được thay đổi thành tám khẩu QF 4 in (100 mm) Mk XVI trên bốn tháp pháo nòng đôi, và chúng được xếp lại lớp như những tàu khu trục phòng không. Legion được đưa ra hoạt động vào ngày 19 tháng 12 năm 1940 với chi phí chế tạo là 445.684 Bảng Anh, không kể đến những trang bị như vũ khí và thiết bị liên lạc do Bộ Hải quân Anh cung cấp. Trong khi chạy thử máy, một số khiếm khuyết bộc lộ, khiến con tàu phải được sửa chữa tại Greenock, Scotland cho đến tháng 1 năm 1941. Nó được cộng đồng cư dân của Borough ở Cheltenham, Gloucestershire đỡ đầu vào tháng 11 năm 1941.